package solution1.demo;

<<<<<<< HEAD:demo/Solution8.java
//import javafx.util.Pair;
//
//import java.util.ArrayList;
//import java.util.Arrays;
//import java.util.List;
//
//public class Solution8 {
//
////    //1.组合总和II
////    private List<List<Integer>> res = new ArrayList<>();
////    private List<Integer> list = new ArrayList<>();
////    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
////        Arrays.sort(candidates);
////        fundCombine(candidates, target, 0);
////        return res;
////    }
////
////    private void fundCombine(int[] candidates, int target, int begin) {
////        if(target == 0) {
////            res.add(new ArrayList<>(list));
////            return;
////        }
////        for(int i = begin; i < candidates.length; i++) {
////            if(target - candidates[i] < 0) {
////                continue;
////            }
////            if(i > begin && candidates[i] == candidates[i - 1]) {
////                continue;
////            }
////            list.add(candidates[i]);
////            fundCombine(candidates, target - candidates[i], i + 1);
////            list.remove(list.size() - 1);
////        }
////    }
//
////    //2.分割回文子串(回溯)
////    private List<List<String>> res = new ArrayList<>();
////    private List<String> list = new ArrayList<>();
////    public List<List<String>> partition(String s) {
////        fundPartDFS(s, 0);
////        return res;
////    }
////
////    private boolean isPlain(String s) {
////        int left = 0;
////        int right = s.length() - 1;
////        while(left < right) {
////            if(s.charAt(left) != s.charAt(right)) {
////                return false;
////            }
////            left++;
////            right--;
////        }
////        return true;
////    }
////
////    private void fundPartDFS(String s, int begin) {
////        if(begin >= s.length()) {
////            res.add(new ArrayList<>(list));
////            return;
////        }
////        for(int i = begin; i < s.length(); i++) {
////            String s1 = s.substring(begin, i + 1);
////            //判断 s1 是否回文
////            if(!isPlain(s1)) {
////                //如果不回文，就没必要继续这层递归了
////                continue;
////            }
////            list.add(s1);
////            fundPartDFS(s, i + 1);
////            list.remove(list.size() - 1);
////        }
////    }
//
////    //3.复原 IP 地址(回溯)
////    private List<String> res = new ArrayList<>();
////    private List<String> path = new ArrayList<>();//用来存放每一组数据
////    public List<String> restoreIpAddresses(String s) {
////        if(s.length() < 4) {
////            return res;
////        }
////        fundIpDFS(s, 0);
////        return res;
////    }
////
////    private void fundIpDFS(String s, int begin) {
////        if(path.size() == 4 && begin == s.length()) {
////            StringBuilder sb = new StringBuilder();
////            for(int i = 0; i < 4; i++) {
////                if(i != 3) {
////                    sb.append(path.get(i));
////                    sb.append(".");
////                } else {
////                    sb.append(path.get(i));
////                }
////            }
////            res.add(sb.toString());
////        } else if(path.size() > 4) {
////            return;
////        }
////        for(int i = begin; i < s.length(); i++) {
////            String s1 = s.substring(begin, i + 1);
////            //校验 IP 是否合理
////            if(!isValue(s1)) {
////                continue;
////            }
////            path.add(s1);
////            fundIpDFS(s, i + 1);
////            path.remove(path.size() - 1);
////        }
////    }
////
////    private boolean isValue(String s) {
////        if(s.length() == 1) {
////            return true;
////        }
////        if(s.length() > 3) {
////            return false;
////        }
////        if(Integer.parseInt(s) > 255) {
////            return false;
////        }
////        if(s.length() > 1 && s.charAt(0) == '0') {
////            return false;
////        }
////        return true;
////    }
//
////    //4.子集(回溯)
////    private List<List<Integer>> res = new ArrayList<>();
////    private List<Integer> path = new ArrayList<>();
////    public List<List<Integer>> subsets(int[] nums) {
////        fundSubsets(nums, 0);
////        return res;
////    }
////
////    private void fundSubsets(int[] nums, int begin) {
////        if(begin <= nums.length) {
////            res.add(new ArrayList<>(path));
////        } else {
////            return;
////        }
////        for(int i = begin; i < nums.length; i++) {
////            path.add(nums[i]);
////            fundSubsets(nums, i + 1);
////            path.remove(path.size() - 1);
////        }
////    }
//
////    //5.子集II(回溯)
////    private List<List<Integer>> res = new ArrayList<>();
////    private List<Integer> list = new ArrayList<>();
////    public List<List<Integer>> subsetsWithDup(int[] nums) {
////        Arrays.sort(nums);
////        fundSubSets(nums, 0);
////        return res;
////    }
////
////    private void fundSubSets(int[] nums, int begin) {
////        if(begin <= nums.length) {
////            res.add(new ArrayList<>(list));
////        } else {
////            return;
////        }
////        for(int i = begin; i < nums.length; i++) {
////            if(i > begin && i > 0 && nums[i] == nums[i - 1]) {
////                continue;
////            }
////            list.add(nums[i]);
////            fundSubSets(nums, i + 1);
////            list.remove(list.size() - 1);
////        }
////    }
//
////    //6.递增子序列(set 层去重)
////    private List<List<Integer>> res = new ArrayList<>();
////    private List<Integer> path = new ArrayList<>();
////    public List<List<Integer>> findSubsequences(int[] nums) {
////        subsequenTrack(nums, 0);
////        return res;
////    }
////
////    private void subsequenTrack(int[] nums, int begin) {
////        if(path.size() >= 2 && path.size() <= nums.length) {
////            res.add(new ArrayList<>(path));
////        } else if(path.size() > nums.length) {
////            return;
////        }
////        //set对本层进行去重
////        Set<Integer> set =  new HashSet<>();
////
////        for(int i = begin; i < nums.length; i++) {
////            //去重
////            if(set.contains(nums[i])) {
////                continue;
////            }
////            //维护递增
////            if(!path.isEmpty() && path.get(path.size() - 1) > nums[i]) {
////                continue;
////            }
////            set.add(nums[i]);
////            path.add(nums[i]);
////            subsequenTrack(nums, i + 1);
////            path.remove(path.size() - 1);
////        }
////    }
//
////    //7.全排列
////    private List<List<Integer>> res = new ArrayList<>();
////    private List<Integer> path = new ArrayList<>();
////    public List<List<Integer>> permute(int[] nums) {
////        permuteTrack(nums);
////        return res;
////    }
////
////    private void permuteTrack(int[] nums) {
////        if(path.size() == nums.length) {
////            res.add(new ArrayList<>(path));
////            return;
////        } else if(path.size() > nums.length) {
////            return;
////        }
////        for(int i = 0; i < nums.length; i++) {
////            if(path.contains(nums[i])) {
////                continue;
////            }
////            path.add(nums[i]);
////            permuteTrack(nums);
////            path.remove(path.size() - 1);
////        }
////    }
//
////    //8.全排列(解法2)
////    private List<List<Integer>> res = new ArrayList<>();
////    private List<Integer> path = new ArrayList<>();
////    public List<List<Integer>> permute(int[] nums) {
////        //排列中一个元素只能用一次，因此使用一个 boolean 数组记录哪些元素是使用过的
////        boolean[] flag = new boolean[nums.length];
////        permuteTrack(nums, flag);
////        return res;
////    }
////
////    private void permuteTrack(int[] nums, boolean[] flag) {
////        if(path.size() == nums.length) {
////            res.add(new ArrayList<>(path));
////            return;
////        } else if(path.size() > nums.length) {
////            return;
////        }
////        for(int i = 0; i < nums.length; i++) {
////            if(flag[i]) {
////                continue;
////            }
////            flag[i] = true;
////            path.add(nums[i]);
////            permuteTrack(nums, flag);
////            path.remove(path.size() - 1);
////            flag[i] = false;
////        }
////    }
//
////    //9.全排列II
////    private List<List<Integer>> res = new ArrayList<>();
////    private List<Integer> list = new ArrayList<>();
////    public List<List<Integer>> permuteUnique(int[] nums) {
////        Arrays.sort(nums);
////        boolean[] path = new boolean[nums.length];
////        permuteTrack(nums, path);
////        return res;
////    }
////
////    private void permuteTrack(int[] nums, boolean[] path) {
////        if(list.size() == nums.length) {
////            res.add(new ArrayList<>(list));
////            return;
////        } else if(list.size() > nums.length) {
////            return;
////        }
////        for(int i = 0; i < nums.length; i++) {
////            if(path[i]) {
////                continue;
////            }
////            if(i > 0 && nums[i] == nums[i - 1] && !path[i - 1])  {
////                continue;
////            }
////            path[i] = true;
////            list.add(nums[i]);
////            permuteTrack(nums, path);
////            list.remove(list.size() - 1);
////            path[i] = false;
////        }
////    }
//
//    //10.n 皇后(回溯 + 模拟)
//    private List<List<String>> res = new ArrayList<>();
//    public List<List<String>> solveNQueens(int n) {
//        //创建棋盘
//        char[][] board = new char[n][n];
//        for(char[] b : board) {
//            Arrays.fill(b, '.');
//        }
//        nQueensTrack(board, n, 0);
=======

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution8 {

//    //1.组合总和II
//    private List<List<Integer>> res = new ArrayList<>();
//    private List<Integer> list = new ArrayList<>();
//    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//        Arrays.sort(candidates);
//        fundCombine(candidates, target, 0);
>>>>>>> ff3f488e325d7766c3bd91ad5d1691e123de9b38:solution1/demo/Solution8.java
//        return res;
//    }
//
//    private List<String> change(char[][] board) {
//        List<String> list = new ArrayList<>();
//        for(int i = 0; i < board.length; i++) {
//            StringBuilder stringBuilder = new StringBuilder();
//            for(int j = 0; j < board[0].length; j++) {
//                stringBuilder.append(board[i][j]);
//            }
//            list.add(stringBuilder.toString());
//        }
//        return list;
//    }
//
//    private void nQueensTrack(char[][] board, int n, int row) {
//        if(n == row) {
//            //将矩阵转化为 list<String>
//            List<String> list = change(board);
//            res.add(list);
//            return;
//        }
//        for(int i = 0; i < n; i++) {
//            //判断当前行当前列是否可以落子
//            if(isValue(board, n, row, i)) {
//                board[row][i] = 'Q';
//                nQueensTrack(board, n, row + 1);
//                board[row][i] = '.';
//            }
//        }
//    }
//
//    private boolean isValue(char[][] board, int n, int row, int col) {
//        //判断当前列是否有其他皇后
//        for(int i = 0; i < row; i++) {
//            if(board[i][col] == 'Q') {
//                return false;
//            }
//        }
//        //左斜角
//        for(int i = row, j = col; i >= 0 && j >= 0; i--,j--) {
//            if(board[i][j] == 'Q') {
//                return false;
//            }
//        }
//        //右斜角
//        for(int i = row, j = col; i >= 0 && j < n; i--,j++) {
//            if(board[i][j] == 'Q') {
//                return false;
//            }
//        }
//        return true;
//    }
//
//
//}
